package com.javaDemo.ti;

import java.util.Arrays;

/**
 * 查找数组中小于给定数n的最大值的算法实现
 * 
 * @ClassName: MaxLessThanN
 * @Description: 实现了三种不同的算法来查找数组中小于给定数n的最大值
 * @author: Your Name
 * @date: 2024/01/20
 * 
 * 问题描述：
 * 给定一个整数数组和一个目标值n，找出数组中小于n的最大整数。
 * 如果不存在这样的整数，则返回-1。
 * 
 * 算法思想：
 * 本类实现了三种不同的解法，分别是：
 * 1. 遍历法：直接遍历数组，记录小于n的最大值
 * 2. 排序后二分查找法：先排序，再用二分查找定位
 * 3. 维护最大值法：遍历时维护一个最大值变量
 * 
 * 这三种方法各有优缺点，适用于不同的场景：
 * - 遍历法：简单直观，适合小规模数据
 * - 二分查找法：对于大规模且需要多次查询的数据更高效
 * - 维护最大值法：本质上也是遍历，但实现更简洁
 */
public class MaxLessThanN {

    /**
     * 方法1：遍历法查找小于n的最大值
     * 
     * 算法复杂度：
     * - 时间复杂度：O(n)，其中n为数组长度
     * - 空间复杂度：O(1)
     * 
     * 实现思路：
     * 1. 遍历数组中的每个元素
     * 2. 记录遍历过程中小于目标值n的最大数
     * 3. 返回最终结果
     * 
     * 举例说明：
     * 数组[1,5,3,9,7,6,4,2,8]，目标值n=6
     * 1. 初始maxLessThanN = -1
     * 2. 遍历元素：
     *    - 1 < 6，更新maxLessThanN = 1
     *    - 5 < 6，更新maxLessThanN = 5
     *    - 3 < 6，但3 < maxLessThanN，不更新
     *    - 9 > 6，不更新
     *    - 7 > 6，不更新
     *    - 6 == 6，不更新
     *    - 4 < 6，但4 < maxLessThanN，不更新
     *    - 2 < 6，但2 < maxLessThanN，不更新
     *    - 8 > 6，不更新
     * 3. 最终结果：maxLessThanN = 5
     *
     * @param arr 输入数组
     * @param n   目标值
     * @return 返回数组中小于n的最大值，如果不存在返回-1
     */
    public static int findMaxLessThanNByTraversal(int[] arr, int n) {
        // 处理边界情况：空数组或null
        if (arr == null || arr.length == 0) {
            return -1;
        }

        // 初始化结果为-1，表示尚未找到小于n的数
        int maxLessThanN = -1;
        
        // 遍历数组中的每个元素
        for (int num : arr) {
            // 如果当前元素小于n且大于当前记录的最大值，则更新最大值
            if (num < n && num > maxLessThanN) {
                maxLessThanN = num;
            }
        }
        
        // 返回找到的最大值，如果没有找到则返回初始值-1
        return maxLessThanN;
    }

    /**
     * 方法2：排序后二分查找法
     * 
     * 算法复杂度：
     * - 时间复杂度：O(nlogn)，其中n为数组长度（主要是排序的时间复杂度）
     * - 空间复杂度：O(1)，不考虑排序的额外空间
     * 
     * 实现思路：
     * 1. 先对数组进行排序
     * 2. 使用二分查找找到最后一个小于n的数
     * 3. 返回查找结果
     * 
     * 举例说明：
     * 数组[1,5,3,9,7,6,4,2,8]，目标值n=6
     * 1. 排序后：[1,2,3,4,5,6,7,8,9]
     * 2. 二分查找过程：
     *    - 初始：left=0, right=8
     *    - mid=4, arr[mid]=5 < 6，left=mid=4
     *    - mid=6, arr[mid]=7 > 6，right=mid-1=5
     *    - mid=5, arr[mid]=6 == 6，right=mid-1=4
     *    - left=4, right=4, mid=4, arr[mid]=5 < 6，left=mid=4
     *    - left=4, right=4，循环结束
     * 3. 最终结果：arr[left]=5
     *
     * @param arr 输入数组
     * @param n   目标值
     * @return 返回数组中小于n的最大值，如果不存在返回-1
     */
    public static int findMaxLessThanNByBinarySearch(int[] arr, int n) {
        // 处理边界情况：空数组或null
        if (arr == null || arr.length == 0) {
            return -1;
        }

        // 对数组进行排序
        Arrays.sort(arr);

        // 使用二分查找
        int left = 0;
        int right = arr.length - 1;

        // 如果最小值都大于等于n，则不存在答案
        if (arr[left] >= n) {
            return -1;
        }

        // 如果最大值小于n，则最大值就是答案
        if (arr[right] < n) {
            return arr[right];
        }

        // 二分查找最后一个小于n的数
        while (left < right) {
            // 防止整数溢出的中间值计算方法
            // 注意这里+1是为了向上取整，确保能找到最后一个小于n的数
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] < n) {
                // 中间值小于n，可能是答案，继续向右找更大的
                left = mid;
            } else {
                // 中间值大于等于n，不可能是答案，向左找
                right = mid - 1;
            }
        }

        // 返回找到的最后一个小于n的数
        return arr[left];
    }

    /**
     * 方法3：维护最大值法
     * 
     * 算法复杂度：
     * - 时间复杂度：O(n)，其中n为数组长度
     * - 空间复杂度：O(1)
     * 
     * 实现思路：
     * 1. 遍历数组，维护一个小于n的最大值
     * 2. 每次遇到一个小于n的数，就更新最大值
     * 3. 返回最终的最大值
     * 
     * 说明：
     * 这种方法本质上与方法1相同，但使用了Math.max简化了代码
     * 在某些情况下可能更易读，但算法复杂度相同
     *
     * @param arr 输入数组
     * @param n   目标值
     * @return 返回数组中小于n的最大值，如果不存在返回-1
     */
    public static int findMaxLessThanNByHeap(int[] arr, int n) {
        // 处理边界情况：空数组或null
        if (arr == null || arr.length == 0) {
            return -1;
        }

        // 初始化结果为-1，表示尚未找到小于n的数
        int maxLessThanN = -1;
        
        // 遍历数组中的每个元素
        for (int num : arr) {
            // 如果当前元素小于n，则更新最大值
            // 使用Math.max简化比较逻辑
            if (num < n) {
                maxLessThanN = Math.max(maxLessThanN, num);
            }
        }
        
        // 返回找到的最大值
        return maxLessThanN;
    }

    /**
     * 主方法：用于测试各种实现方法
     * 
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 测试用例1：标准情况
        int[] arr1 = {1, 5, 3, 9, 7, 6, 4, 2, 8};
        int n1 = 6;
        System.out.println("测试用例1 - 标准情况：");
        System.out.println("数组：" + Arrays.toString(arr1));
        System.out.println("目标值n = " + n1);
        
        // 测试方法1：遍历法
        System.out.println("\n方法1（遍历法）结果：" + 
            findMaxLessThanNByTraversal(arr1, n1));
        
        // 测试方法2：二分查找法
        System.out.println("方法2（二分查找法）结果：" + 
            findMaxLessThanNByBinarySearch(arr1.clone(), n1));
        
        // 测试方法3：维护最大值法
        System.out.println("方法3（维护最大值法）结果：" + 
            findMaxLessThanNByHeap(arr1, n1));

        // 测试用例2：边界情况 - 单元素数组
        int[] arr2 = {1};
        int n2 = 1;
        System.out.println("\n测试用例2 - 单元素数组：");
        System.out.println("数组：" + Arrays.toString(arr2));
        System.out.println("目标值n = " + n2);
        System.out.println("方法1结果：" + findMaxLessThanNByTraversal(arr2, n2));
        System.out.println("方法2结果：" + findMaxLessThanNByBinarySearch(arr2.clone(), n2));
        System.out.println("方法3结果：" + findMaxLessThanNByHeap(arr2, n2));

        // 测试用例3：特殊情况 - 空数组
        int[] arr3 = {};
        int n3 = 5;
        System.out.println("\n测试用例3 - 空数组：");
        System.out.println("数组：" + Arrays.toString(arr3));
        System.out.println("目标值n = " + n3);
        System.out.println("方法1结果：" + findMaxLessThanNByTraversal(arr3, n3));
        System.out.println("方法2结果：" + findMaxLessThanNByBinarySearch(arr3, n3));
        System.out.println("方法3结果：" + findMaxLessThanNByHeap(arr3, n3));
        
        // 测试用例4：特殊情况 - 所有元素都大于等于目标值
        int[] arr4 = {10, 20, 30, 40, 50};
        int n4 = 10;
        System.out.println("\n测试用例4 - 所有元素都大于等于目标值：");
        System.out.println("数组：" + Arrays.toString(arr4));
        System.out.println("目标值n = " + n4);
        System.out.println("方法1结果：" + findMaxLessThanNByTraversal(arr4, n4));
        System.out.println("方法2结果：" + findMaxLessThanNByBinarySearch(arr4.clone(), n4));
        System.out.println("方法3结果：" + findMaxLessThanNByHeap(arr4, n4));
        
        // 测试用例5：特殊情况 - 所有元素都小于目标值
        int[] arr5 = {1, 2, 3, 4, 5};
        int n5 = 10;
        System.out.println("\n测试用例5 - 所有元素都小于目标值：");
        System.out.println("数组：" + Arrays.toString(arr5));
        System.out.println("目标值n = " + n5);
        System.out.println("方法1结果：" + findMaxLessThanNByTraversal(arr5, n5));
    }
}